'''判断质数'''
# 法一：直接循环判断
def is_prime(num):
    if num <= 3:
        return num > 1
    for i in range(2, num):
        if (num % i) == 0:
            return False
    return True

# 法二：
# 假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。
# 由此可以优化循环次数。

def is_prime1(num):
    if num <= 3:
        return num > 1
    for i in range(2, int(num ** 0.5)):
        if (num % i) == 0:
            return False
    return True

# 法三：继续优化
# 我们继续分析，其实质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，
# 其中 x 是大于等于1的自然数。

# 论证这个结论：
# 首先 6x 肯定不是质数，因为它能被 6 整除；
# 其次 6x+2 肯定也不是质数，因为它还能被2整除；
# 依次类推，6x+3 肯定能被 3 整除；
# 6x+4 肯定能被 2 整除。
# 那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。
# 所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。

def is_prime2(num):
    if num <= 3:
        return num > 1
    # 不符合条件肯定不是质数
    if num % 6 != 1 and num % 6 != 5:
        return False
    # 确认是不是质数，只需要判断有没有质数因子
    for i in range(5, int(num ** 0.5), 6):
        if (num % i == 0 or num % (i + 2) == 0):
            return False
    return True

num = int(input("输入数字："))
if is_prime1(num):
    print('%d是质数'%num)
else:
    print('%d不是质数'%num)

